package leetcode

import "fmt"

// Trie Trie
type Trie struct {
	val      byte
	children []*Trie
	endpoint bool
}

// Constructor Initialize a trie
func Constructor() Trie {
	children := make([]*Trie, 26)
	return Trie{
		val:      0,
		children: children,
		endpoint: false,
	}
}

// Insert Inserts a word into the trie.
func (t *Trie) Insert(word string) {
	wordlen := len(word)
	path := t
	for i := wordlen - 1; i >= 0; i-- {
		idx := word[i] - 'a'
		if path.children[idx] == nil {
			newT := Constructor()
			newT.val = word[i]
			path.children[idx] = &newT
			path = &newT
		} else {
			path = path.children[idx]
		}
		if i == 0 {
			path.endpoint = true
		}
	}
}

// ToString Returns strings
func (t *Trie) ToString() int {
	alllen := 0
	for i := 0; i < len(t.children); i++ {
		if t.children[i] != nil {
			sublen := 0
			toString(t.children[i], "", &sublen)
			alllen += sublen
		}
	}
	return alllen
}

func toString(t *Trie, parent string, sublen *int) {
	hasSon := false
	parent += string(t.val)
	for i := 0; i < len(t.children); i++ {
		if t.children[i] != nil {
			toString(t.children[i], parent, sublen)
			hasSon = true
		}
	}

	if !hasSon {
		parent += "#"
		*sublen += len(parent)
	}
}

// ToString1 Returns strings
func (t *Trie) ToString1() string {
	son := ""
	for i := 0; i < len(t.children); i++ {
		if t.children[i] != nil {
			son += t.children[i].ToString1()
		}
	}
	if t.val != 0 {
		son += string(t.val)
	}
	if t.endpoint {
		son += "#"
		fmt.Print(son)
	}
	return son
}

// Search Returns if the word is in the trie
func (t *Trie) Search(word string) bool {
	wordlen := len(word)
	path := t
	for i := 0; i < wordlen; i++ {
		idx := word[i] - 'a'
		if path.children[idx] != nil {
			path = path.children[idx]
		} else {
			return false
		}
		if i == wordlen-1 {
			return path.endpoint
		}
	}
	return false
}

// StartsWith Returns if there is any word in the trie that starts with the given prefix
func (t *Trie) StartsWith(prefix string) bool {
	wordlen := len(prefix)
	if wordlen == 0 {
		return false
	}
	path := t
	for i := 0; i < wordlen; i++ {
		idx := prefix[i] - 'a'
		if path.children[idx] != nil {
			path = path.children[idx]
		} else {
			return false
		}
	}
	return true
}
